package DP;

/**
 * 53.最大子数组和  （动态规划解法，之前是贪心）
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组是数组中的一个连续部分。
 * dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]
 * dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
 * nums[i]，即：从头开始计算当前连续子序列和
 */
public class maxSubArray {
    /**
     * 一刷
     */
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        ans = dp[0];
        for (int i = 1; i < nums.length; i++){
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }
    /**
     * 二刷
     */
    class Solution {
        public int maxSubArray(int[] nums) {
            int dp[] = new int[nums.length];
            dp[0] = nums[0];
            int result = dp[0];
            for (int i = 1; i < nums.length; i++) {
                dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
                result = Math.max(result, dp[i]);
            }
            return result;
        }
    }
}
